package com.demo21_合并两个升序链表;
/*
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

class Solution {

}
 */
public class Test21 {
    public static void main(String[] args) {

    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode head;
        ListNode r1,r2;
        ListNode p1,p2;

        if(list1!=null) {
             head=new ListNode(0,list1);
             r1=list2;
             r2=list2;
             p1=list1;
             p2=head;
        }else if(list2!=null){
             head=new ListNode(0,list2);
             r1=list1;
             r2=list1;
             p1=list2;
             p2=head;
        }else {
            return null;
        }
        while (r1!=null&&p1!=null){
            if(r1.val< p1.val){
                r1=r1.next;
                p2.next=r2;
                r2.next=p1;
                p2=r2;
                r2=r1;
            }else {
                p2=p1;
                p1=p1.next;
            }

            if(p1==null){
                p2.next=r1;
            }
        }
        return head.next;

    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val; this.next = next;
    }
}
